package day5;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class ch1 {


    //94
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root,list);
        return list;

    }
    public void  dfs(TreeNode node,List<Integer> list){

        if(node==null) return;
        dfs(node.left,list);
        list.add(node.val);
        dfs(node.right,list);

    }
    //104
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
    //226
    public TreeNode invertTree(TreeNode root) {
        fun(root);
        return root;
    }

    public void fun(TreeNode root){
        if(root==null) return;
        TreeNode l = root.left;
        TreeNode r = root.right;
        root.left = r;
        root.right = l;
        fun(r);
        fun(l);
    }
    //101
    public boolean isSymmetric(TreeNode root) {

        return cal(root.left,root.right);

    }

    public boolean cal(TreeNode m,TreeNode n){
        if(m==null&&n==null) return true;

        int x = m==null?-1:m.val;
        int y = n==null?-1:n.val;
        if(x!=y){
            return false;
        }else{
            return cal(m.right,n.left)&&cal(n.right,m.left);
        }
    }

    //543

    public  static  int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
       kcl(root);
       return max-1;

    }

    public int kcl(TreeNode root){
        if(root==null) return 0;

        int l = diameterOfBinaryTree(root.left);
        int r = diameterOfBinaryTree(root.right);
        max = Math.max(max,l+r+1);

        return Math.max(l,r)+1;
    }


    //108
    public TreeNode sortedArrayToBST(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        df(nums,root,left,mid-1,mid+1,right);
        return root;
    }

    public void df(int[] nums,TreeNode root,int l,int r,int m,int n){
        if(l<=r){
            int mid = (l+r)/2;
            TreeNode left = new TreeNode(nums[mid]);
            root.left=left;
            df(nums,left,l,mid-1,mid+1,r);
        }
        if(m<=n){
            int mid = (m+n)/2;
            TreeNode right = new TreeNode(nums[mid]);
            root.right=right;
            df(nums,right,m,mid-1,mid+1,n);
        }
    }

    //437
    public static int sum = 0;
    public int pathSum(TreeNode root, int targetSum) {
        sum = 0;
        HashMap<Long,Integer> map = new HashMap<>();
        map.put(0L,1);
        gh(root,targetSum,map);
        return sum;
    }

    public void gh(TreeNode node,int targetSum,HashMap<Long,Integer> map){
        if (node==null) return;
        int num = targetSum-node.val;
        HashMap<Long,Integer> m = new HashMap<>();
        sum += map.getOrDefault(num,0);
        for (Long k: map.keySet()){
            long newK = k+node.val;
            int in = map.get(k);
            m.put(newK,in);
        }
        m.put(0l,m.getOrDefault(0,0)+1);
        gh(node.left,targetSum,m);
        gh(node.right,targetSum,m);
    }



}
